﻿#define _CRT_SECURE_NO_WARNINGS 1

//446. 等差数列划分 II - 子序列
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        //优化
        unordered_map<long long, vector<int>> hash;
        for (int i = 0; i < n; ++i)
            hash[nums[i]].push_back(i);

        vector<vector<int>> dp(n, vector<int>(n));//创建 dp 表 + 初始化
        int ret = 0;
        for (int j = 2; j < n; ++j)// 固定倒数第⼀个数
        {
            for (int i = 1; i < j; ++i)// 枚举倒数第⼆个数
            {
                long long a = (long long)2 * nums[i] - nums[j];//处理数据溢出
                if (hash.count(a))
                {
                    for (auto k : hash[a])
                    {
                        if (k < i)
                            dp[i][j] += dp[k][i] + 1;
                        else
                            break;

                    }
                    ret += dp[i][j];
                }
            }
        }
        return ret;


    }
};